package com.leetcode.专项突破.排序算法全解析;

import com.leetcode.common.utils.ArrayUtils;
import java.util.Arrays;

/**
 * @author 覃国强
 * @date 2022-05-13 17:52
 */
public class B03_归并排序 {

  public static void main(String[] args) {
    MergeSort mergeSort = new MergeSort();
    int[] arr = ArrayUtils.randomArr(20);
    System.out.println("origin: " + Arrays.toString(arr));
    mergeSort.sort(arr);
    System.out.println("sorted: " + Arrays.toString(arr));
  }

  static class MergeSort {

    public void sort(int[] arr) {
      if (arr == null || arr.length == 0) {
        return;
      }
      int[] answer = new int[arr.length];
      sort(arr, 0, arr.length - 1, answer);
    }

    private void sort(int[] arr, int start, int end, int[] answer) {
      if (start < end) {
        int mid = (start + end) / 2;
        sort(arr, start, mid, answer);
        sort(arr, mid + 1, end, answer);
        merge(arr, start, mid, end, answer);
      }
    }

    private void merge(int[] arr, int start, int mid, int end, int[] answer) {
      int left = start;
      int right = mid + 1;
      int index = start;
      while (left <= mid && right <= end) {
        answer[index++] = arr[left] < arr[right] ? arr[left++] : arr[right++];
      }
      while (left <= mid) {
        answer[index++] = arr[left++];
      }
      while (right <= end) {
        answer[index++] = arr[right++];
      }

      for (int i = start; i <= end; ++i) {
        arr[i] = answer[i];
      }
    }
  }

}
